<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 6. Комбинаторика.</h2>
<ol>
  <li>Генерация всех объектов рекурсивным перебором в лексикографическом и антилексикографическом порядке.</li>
  <li>Вывод всех перестановок длины n</li>
  <ol>
    <li>Рекурсивная реализация за O(n! * n)</li>
    <li>Рекурсивная реализация за O(n!) [используем очередь]</li>
  </ol></li>
  <li>Нахождение следующего (предыдущего) объекта в лексикографическом порядке.</li>
  <li>Подсчет количества объектов динамикой.</li>
  <li>Нахождение k-го в лексикографическом порядке объекта (после того, как посчитали динамику)</li>
  <li>Нахождение лексикографически минимального объекта (жадность)</li>
  <li>Нахождение количества "хороших" объектов на отрезке от L до R (после того, как посчитали динамику и используя прием "R - L")</li>
  <li>Примеры [L..R] задач (L, R <= 10<sup>18</sup>)</li>
  <ol>
    <li>Количество чисел от L до R, кратных m (халявка)</li>
    <li>Количество чисел из цифр 1 и 2 от L до R</li>
    <li>Сумма всех чисел из цифр 1 и 2 от L до R</li>
    <li>Количество чисел из цифр 1 и 2 от L до R, кратных m (m &lt; 100)</li>
    <li>Количество чисел из цифр 1 и 2 от L до R с суммой цифр ровно s (s &le; 100).</li>
    <li>Количество чисел от L до R, являющихся палиндромами</li>
    <li>Количество чисел от L до R с ровно k нулями в двоичной записи</li>
  </ol></li>
  <li>Примеры задачи "следующий лексикографически"</li>
  <ol>
    <li>Следующая перестановка (N &le; 10<sup>6</sup>)</li>
    <li>Следующая скобочная последовательность (N &le; 10<sup>6</sup>, open < close)</li>
    <li>Следующее разбиение на возрастающие слагаемые (N &le; 10<sup>6</sup>)</li>
  </ol></li>
  <li>Примеры задач "k-й объект"</li>
  <ol>
    <li>k-я лексикографически строка длины N, состоящая только из 0 и 1</li>
    <li>k-я лексикографически строка длины N, без двух единиц подряд</li>
    <li>k-я лексикографически строка длины не более N, без двух единиц подряд</li>
    <li>k-я лексикографически строка из 1 и 2 с суммой цифр ровно s (s &le; 100).</li>
    <li>k-е разбиение на возрастающие слагаемые</li>
  </ol></li>
</ol>
